The importance of error correction coding of data in digital computer systems has increased greatly as the density of the data recorded on mass storage media, more particularly disks, has increased. With higher recording densities, a tiny imperfection in the recording surface of a disk can corrupt a large amount of data. In order to avoid losing that data, error correction codes ("ECC's") are employed to, as the name implies, correct the erroneous data.
Before a string of data symbols is written to a disk, it is mathematically encoded to form ECC symbols. The ECC symbols are then appended to the data string to form data code words--data symbols plus ECC symbols--and the data code words are written to or stored on the disks. When data is to be read from the disks, the data code words containing the data symbols to be read are retrieved from the disks and mathematically decoded. During decoding any errors in the data are detected and, if possible, corrected through manipulation of the ECC symbols For a detailed description of decoding see Peterson and Weldon, Error Correction Codes, 2d Edition, MIT Press, 1972!.
Stored digital data can contain multiple errors. One of the most effective types of ECC used for the correction of multiple errors is a Reed-Solomon code For a detailed description of Reed-Solomon codes, see Peterson and Weldon, Error Correction Codes!. To correct multiple errors in strings of data symbols, Reed-Solomon codes efficiently and effectively utilize the various mathematical properties of sets of symbols known as Galois Fields, represented "GF(P.sup.q)", where "P" is a prime number and "q" can be thought of as the number of digits, base P, in each element or symbol in the field. "P" usually has the value 2 in digital computer applications and, therefore, "q" is the number of bits in each symbol.
To correct errors in the data code words, the error syndrome polynomial is produced. The error syndrome polynomial is used, in turn, to produce error locator and error evaluator polynomials, which are used, respectively, to determine the locations and values of the code word errors.
In many prior known systems separate encoders and decoders are used to encode and decode the data code words. Thus, there is hardware that is not in use for one of the encoding or decoding operations.
In certain other prior known systems the decoders are modified, to also perform the encoding operation. These systems generally use a hardware configuration that is described in a 1992 article by Fettweis and Hassner entitled "A combined Reed-Solomon Encoder and Syndrome Generator with Small Hardware Complexity," IEEE Int. Symp. on Circuits and Systems pp. 1871-1874. This hardware saves on gate count over the separate encoder and decoder, but has latency problems, as discussed in the article.
We have invented an encoder/decoder that has a reduced gate count over separate encoders and decoders, and does not have the latency problems of the Fettweis and Hassner configuration. A modified version of this encoder/decoder can also be used to encode and decode with the modified Reed Solomon codes described in a co-pending U.S. patent application Ser. No. 08/749,235 entitled MODIFIED REED SOLOMON CODE SELECTION AND ENCODING SYSTEM, which is assigned to a common assignee and included herein by reference. The modified Reed Solomon codes encode w-bit data symbols over GF(2.sup.w+i) to produce (w+i)-bit ECC redundancy symbols. The encoding operations involve further manipulating the (w+i)-bit ECC redundancy symbols and a number of "pseudo redundancy symbols," to form a data code word with symbols in GF(2.sup.w). The decoding operations decode the data code word, including the ECC symbols and the pseudo redundancy symbols, to reproduce error-free w-bit data symbols.